【题解】 [NOI2016]国王饮水记 斜率优化DP loj2087 | Qiuly's blog!

【题解】 [NOI2016]国王饮水记 斜率优化DP loj2087

Posted on | In | Comments:

可爱的题目传送门：戳我戳我·(╹▽╹)·

说实话这道题如果单看斜率优化 $\texttt{DP}$ ，但是如果没猜到那么多结论，你是怎么也想不到”斜率优化”是从哪里来的。那么我们开始猜结论吧……

  • 1. 初始水位小于 $h_1$ 的没有用。

这很显然。

  • 2. 如果 $n\leq k$ ，那么只需要将所以大于 $h_1$ 的跟 $1$ 城市连就好了。

每次连接的城市数越少贡献越大，那么每个逐一连一次一定是最优方案。

  • 3. 每次操作必然跟 $1$ 城市有关系。

不然没贡献。

  • 4. 除了 $1$ 号城市，其他每个城市最多连一次。

因为连过一次的城市的水位已经和 $1$ 城市一样了，简单点说肯定就是废了。

  • 5. 每次连的所有城市中最小的 $h_i$ 必然大于上一次链接的最大的 $h_i$ 。

这很显然，不然不满足最优方案。

  • 6. 将所以城市按水位排序后，每次选择的必然是连续一段区间。

和上一个差不多。

  • 7. 每次选择的区间必然和上一次的选择区间接触。

这很显然。

  • 8. 每次选择的区间的长度必定单调不增。

满足最优，都说了每次连接的城市越少贡献越大。

那么显然就变成了一个区间问题了，我们需要将这个区间分成若干块。

设 $f_{i,j}$ 表示排序后前 $i$ 个城市联通了 $j$ 次后 $1$ 号城市的最大水位高度。那么转移直接枚举一个 $k$ ，在新的一次连接中连接了 $k+1$ 到 $i$ 这些城市。转移方程显然：

*注：$s_i$ 为前缀和。

上式的复杂度为 $O(n^2k)$ ，肯定爆炸。但是这个是可以斜率优化的：

然后通过第 $8$ 条性质可以得知 $\texttt{DP}$ 是有决策单调性的，故复杂度为 $O(nk)$ 。因为恶心的高精度小数的运算还需要 $O(p)$ 的复杂度，所以最终总时间复杂度为 $O(nkp)$ 。

我们发现 $k$ 有 $10^9$ ，所以复杂度带 $k$ 的一定假掉了。

那么观察第 $2$ 条性质会发现，如果 $k$ 大于 $n$ 了直接将 $k$ 设为 $n$ 就好了。也就是说复杂度应该为 $O(n^2p)$ ，这样就是 $86$ 分，通过数据来看会发现这个倾向于大众分，一车厢的人都是这个分数。

那么如果想要 $\texttt{AC}$ 的话需要最后一条很迷的性质：

  • 9. 因为 $h$ 各不同，选择的区间最多只有 $14$ 个区间长度大于 $1$ ，其他的区间均等于 $1$ 。

很迷，准确的说这样的区间是 $O(\log\frac{nh}{\min_i\{h_i-h_{i-1}\}})$ 个。

证明不会……但是这里写了证明(唯一的且很迷的证明)：哈哈我是传送门O(∩_∩)O

那么就丢代码了，实际上是需要高精小数的，这里先给出一个除去高精小数板子的版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=8e3+2;

Decimal ans;
int n,k,p,lim,h[N],s[N],pre[N][16],tot;
int q[N],head,tail;
double f[N][16];
struct point{double x,y;}t[N];
double slope(point a,point b) {return (a.y-b.y)/(a.x-b.x);}

Decimal solve(int i,int j) {
    if(!j) return h[1];
    return (solve(pre[i][j],j-1)+s[i]-s[pre[i][j]])/(i-pre[i][j]+1);
}

int main() {
    scanf("%d%d%d%d",&n,&k,&p,&h[tot=1]);
    for(int i=2;i<=n;++i) {
        scanf("%d\n",&h[i]);
        if(h[i]>h[1]) h[++tot]=h[i];
    }
    n=tot;sort(&h[1],&h[n+1]);
    for(int i=1;i<=n;++i) f[i][0]=h[1];
    for(int i=1;i<=n;++i) s[i]=s[i-1]+h[i];
    k=min(k,n),lim=min(k,14);
    for(int j=1;j<=lim;++j) {
        q[head=tail=1]=1;
        for(int i=1;i<=n;++i) t[i]=(point){i-1,s[i]-f[i][j-1]};
        for(int i=2;i<=n;++i) {
            point now=(point){i,s[i]};
            while(head<tail&&slope(now,t[q[head]])<slope(now,t[q[head+1]])) ++head;
            f[i][j]=(f[q[head]][j-1]+s[i]-s[q[head]])/(i-q[head]+1);
            pre[i][j]=q[head];
            while(head<tail&&slope(t[q[tail]],t[q[tail-1]])>slope(t[q[tail]],t[i])) --tail;
            q[++tail]=i;
        }
    }
    int m=n-k+lim,pos;
    double mx=0;
    for(int i=0;i<=lim;++i) 
        if(f[m][i]>mx) mx=f[m][i],pos=i;
    ans=solve(m,pos);
    for(int i=m+1;i<=n;++i) ans=(ans+h[i])/2;
    cout<<ans.to_string(p<<1)<<endl;
    return 0;
}

那么高精度小数板子的下载链接就贴这了：$loj$ 的下载地址传送们(～￣▽￣)～

本文标题:【题解】 [NOI2016]国王饮水记 斜率优化DP loj2087

文章作者:Qiuly

发布时间:2019年04月29日 - 00:00

最后更新:2019年04月29日 - 21:20

原始链接:http://qiulyblog.github.io/2019/04/29/[题解]loj2087/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。